//
// Created by 杨雪松 on 2023/5/11.
//
#include "main.h"

void return_create_tree(BiTreeNode* root_p, char* pre_order_seq, int* current_index_p, int num_elements) {
    if (*current_index_p < num_elements) {
        root_p->data = pre_order_seq[*current_index_p];
        *current_index_p += 1;

        if (pre_order_seq[*current_index_p] == '#') {
            root_p->leftChild = NULL;
            *current_index_p += 1;
        }
        else {
            root_p->leftChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            return_create_tree(root_p->leftChild, pre_order_seq, current_index_p, num_elements);
        }

        if (pre_order_seq[*current_index_p] == '#') {
            root_p->rightChild = NULL;
            *current_index_p += 1;
        }
        else {
            root_p->rightChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            return_create_tree(root_p->rightChild, pre_order_seq, current_index_p, num_elements);
        }
    }


}
void create_tree(BiTreeNode** root_pp, char* pre_order_seq, int num_elements) {
    *root_pp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    int current_index = 0;

    return_create_tree(*root_pp, pre_order_seq, &current_index, num_elements);
}

void pre_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != NULL) {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);
    }


}

void in_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != NULL) {
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }
}

void post_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != NULL) {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
}

BiTreeNode* search(BiTreeNode* root, DataType x) {
    BiTreeNode* find = NULL;
    if (root != NULL) {
        if (root->data == x) {
            find = root;
        }
        else { //root->data != x
            find = search(root->rightChild, x);
            if (find == NULL) {
                find = search(root->leftChild, x);
            }
        }
    }
    return find;
}

void destroy(BiTreeNode** root) {
    if ((*root) != NULL && (*root)->leftChild != NULL)
        destroy(&(*root)->leftChild);

    if ((*root) != NULL && (*root)->rightChild != NULL)
        destroy(&(*root)->rightChild);

    free(*root);
}


void main(void) {
    BiTreeNode* root, * p, * pp, * find;

    char* pre_order_seq = "ABC##DE#G##F###";
    create_tree(&root, pre_order_seq, 15);

    pre_order_traverse(root, visit); // 输出应该为 A B C D E G F
    printf("\n");
    in_order_traverse(root, visit); // 输出应该为 C B E G D F A
    printf("\n");
    post_order_traverse(root, visit); // 输出应该为 C G E F D B A

    char x = 'E';
    find = search(root, x);
    if (find != NULL)
        printf("\ndata %c is in it \n", x);
    else
        printf("\ndata %c is't in it \n", x);

    x = 'H';
    find = search(root, x);
    if (find != NULL)
        printf("\ndata %c is in it \n", x);
    else
        printf("\ndata %c is't in it \n", x);

    destroy(&root);
}